package com.leetcode.hot100;

import java.util.HashMap;
import java.util.Objects;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-24  19:13
 * @Description: 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * @Version: 1.0
 */
public class 最小覆盖子串_76 {
    public static void main(String[] args) {
        String s = "aa";
        String t = "aa";
        String s1 = minWindow(s, t);
        System.out.println(s1);

    }

    public static String minWindow(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        HashMap<Character, Integer> hashMapS = new HashMap<>();
        HashMap<Character, Integer> hashMapT = new HashMap<>();
        for (char tChar : tChars) {
            hashMapT.put(tChar, hashMapT.getOrDefault(tChar, 0) + 1);
        }
        int left = 0, right = 0, count = 0;
        String result = "";
        while (right < sChars.length) {
            char sChar = sChars[right];
            hashMapS.put(sChar, hashMapS.getOrDefault(sChar, 0) + 1);
            if (hashMapT.containsKey(sChar) &&
                    Objects.equals(hashMapS.get(sChar), hashMapT.get(sChar))) {
                count++;
            }


            while (count == hashMapT.size() && left <= right) {
                // 更新最小覆盖子串信息
                String temp = s.substring(left, right + 1);
                if (result.length() == 0 || temp.length() < result.length()) {
                    result = temp;
                }

                char leftChar = sChars[left];
                hashMapS.put(leftChar, hashMapS.get(leftChar) - 1);
                if (hashMapT.containsKey(leftChar) &&
                        hashMapT.get(leftChar) > hashMapS.get(leftChar)) {
                    count--;
                }
                left++;
            }

            right++;
        }
        return result;

    }

 /*   public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

        int[] tCounts = new int[128]; // ASCII码范围内的数组，用于记录字符串 t 中每个字符的出现次数
        for (char c : t.toCharArray()) {
            tCounts[c]++;
        }

        int left = 0, right = 0; // 定义窗口的左右指针
        int requiredChars = t.length(); // 需要匹配的字符总数
        int formedChars = 0; // 已经匹配的字符总数
        int minLen = Integer.MAX_VALUE; // 最小覆盖子串的长度
        int minStart = 0; // 最小覆盖子串的起始索引
        int[] windowCounts = new int[128]; // 用于记录窗口内字符的出现次数

        while (right < s.length()) {
            // 扩展窗口
            char rightChar = s.charAt(right);
            windowCounts[rightChar]++;

            // 判断是否匹配到 t 中的字符
            if (tCounts[rightChar] > 0 && windowCounts[rightChar] <= tCounts[rightChar]) {
                formedChars++;
            }

            // 尝试缩小窗口
            while (formedChars == requiredChars && left <= right) {
                // 更新最小覆盖子串信息
                int currentLen = right - left + 1;
                if (currentLen < minLen) {
                    minLen = currentLen;
                    minStart = left;
                }

                // 移动左指针
                char leftChar = s.charAt(left);
                windowCounts[leftChar]--;
                if (tCounts[leftChar] > 0 && windowCounts[leftChar] < tCounts[leftChar]) {
                    formedChars--;
                }
                left++;
            }
            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }*/

}
